模拟赛题解/2025.9.4 模拟赛

T1-空洞骑士（bit）

题面

多组询问，每组询问给定一对正整数 $a,b(a\leq b)$，在闭区间 $[a,b]$ 内所有整数中，找到二进制表示中 $1$ 个数最少的数。如果有多个这样的数，找到其中最小的那一个。

$1\leq T\leq2\times10^5,1\leq a\leq b\leq10^{18}$。

题解

考虑直接按位贪心求解。

从最高位开始，在保证 $\leq b$ 的情况下，尽量在高位放 $1$，并且得到的值一旦 $\geq a$ 就跳出。

此时可以保证最终得到的数可以保证在 $[a,b]$ 区间内，并且 $1$ 的数量最少。

再考虑如何求出最小值。

从最高位开始枚举，显然尽量要将 $1$ 往低位放，故除非后续位数全部在最高位放 $1$ 直到放完也 $<a$，否则不放，显然一定最优。

复杂度 $O(T\log V)$。

T2-丝之歌（infected）

题面

有一棵 $n$ 个节点的树，选择两个节点将树切断，得到三个连通块。

设三个连通块的大小分别为 $a,b,c$，求出 $\max\{a,b,c\}-\min\{a,b,c\}$ 的最小值。

$3\leq n\leq2\times10^5$。

题解

三个连通块不好求解，考虑固定其中一个连通块的断点。

此时显然使另外两个连通块大小尽量接近最优，因此我们将所有点的子树大小（记为 $siz$）存入 $\text{multiset}$ 二分求解。

然而当另一个断点是当前断点祖先时，其 $siz$ 包含当前点的 $siz$，所以我们开两个 $\text{multiset}$，分别存储祖先节点和非祖先节点，祖先节点更新答案时减去当前节点的 $siz$ 即可。

复杂度 $O(n\log n)$。

T3-即将于今晚（skill）

题面

有编号为 $1,2,3$ 的三个值，初始时都为 $0$。

可以用 $n$ 次操作对值进行修改，每次操作为：

• 选择其中一个值，设选择的值为 $j$，使其值增加 $a_{i,j}$。
• 对于另外两个值，如果已经有 $x$ 次没有进行操作，则使其值减少 $x$。
• 三个值都不会小于 $0$，会始终和 $0$ 取 $\max$。

求在 $n$ 次操作结束后，三个值之和的最小值。

• $1\leq n\leq 1000$。
• $\forall i,0\leq a_i\leq 10000$。

题解

我们注意到两个性质：

• 如果一个值被修改过，那么将它重新修改到 $0$ 显然不优（可以将修改它的操作变为修改其他值）。
• 对于一个数，它修改后最多被搁置的轮数是 $\sqrt{V}$ 级别的，因为被搁置 $x$ 轮后产生的减值是 $\frac{1}{2}x(x+1)$，而值不会被减到 $0$。

因此我们可以设计状态为 $f_{i,j,k_1,k_2}$，表示进行到第 $i$ 次操作时，本次操作选择的是第 $j$ 个值，下一个值被搁置了 $k_1$ 轮，下下个值被搁置了 $k_2$ 轮。

每个状态向下一个状态的转移显然只有三种可能：

1. 仍选择当前点。
2. 选择下一个点。
3. 选择下下一个点。

此时的转移是显然的。

注意：一个点没有被修改过之前不会产生减法，所以如果 $k_1$ 或 $k_2$ 为 $0$，其转移方向应该为 $0$。

最后我们注意到 $i$ 状态只会从 $i-1$ 转移过来，所以采用滚动数组。

复杂度 $O(n\sqrt{V}^2)=O(nV)$。

T4-十点发售（orandgcd）

题面

给序列 $a_1,\cdots,a_n$，$b_1,\cdots,b_n$，$b_1,\cdots,b_n$。

定义区间 $[l,r]$ 的价值为 $a_l,\cdots,a_r$ 按位与，$b_l,\cdots,b_r$ 按位或，$c_l\cdots,c_r$ 的最大公因数，这三者的乘积。

$m$ 次查询，每次查询给出区间 $[l,r]$，查询满足 $l\leq l'\leq r'\leq r$ 的 $[l',r']$ 的价值之和。

结果对 $2^{32}$ 取模。

$1\leq a_i,b_i,c_i\leq n\leq10^6,1\leq l,r\leq n,1\leq m\leq5\times10^6$。

题解

考虑扫描线，扫到 $r$ 时维护 $A_i,B_i,C_i$ 表示区间 $[i,r]$ 对应运算的答案，$s_i$ 表示左端点在 $[1,i]$ 内，右端点在 $[1,r]$ 内的区间的权值和（相当于 $A_kB_kC_k(k\leq i)$ 的历史和，虽然这道题并不需要用到历史和），那么询问 $[l,r]$ 的答案可以拆分为扫到 $r$ 时的 $s_r−s_{l−1}$。

一个并不是很显然的结论是：扫描线 $r\rightarrow r+1$，$A_iB_iC_i$ 的值只有一段 $[r−p,r]$ 会 改变，然后这个 $p$ 的大小是均摊 $O(\log V)$ 的。具体证明可以考虑拆位，每一位会在什 么时候改变这个乘积。

于是我们就可以维护 $D_i=A_iB_iC_i$ 这个数组了，对于 $[1,r−p)$ 这一段的 $D_i$ 没有发生改变，但是 $s_i$ 改变了，直接历史和复杂度又太巨大了，可以考虑将 $s_i$ 的定义式改为 $s_i=val_i+D[1,i]*r$，这样只要前缀 $D$ 不改变，$s$ 也不用修改，需要求值的时候算一下就行。

总复杂度 $O(n\log V+m)$。另外本题有一个数据不变，时限 3s->1s 的版本（P9335）。